Le Song
Abstract :
Recently, there is a surge of interests in using graph neural networks (GNNs) to learn distributed local
algorithms on graphs. However, these works focus more on imitating existing algorithms, and are limited in two
important aspects: the search space for algorithms is too small and the learned GNN models are not interpretable.
To address these issues, we propose a novel framework which enlarge the search space using cheap global
information from tree decomposition of the graphs, and can explain the structures of the graph leading to the
decision of learned algorithms. We apply our framework to three NP-complete problems on graphs and show that the
framework is able to discover effective and explainable distributed local algorithms.